
public class SwapSort extends Sort {
	public void sort() {}
}

class BubbleSort extends SwapSort {
	
	public void sort() {
		printArray();
		for(int i=m_count-1; i>=1; --i) {
			boolean flag = true;
			for(int j=0; j<i; ++j) {
				if (m_array[j].gt(m_array[j+1])) {
					m_array[j].swap(m_array[j+1]);
					flag = false;
				}
			}
			if (flag) break;
			printArray();
		}
	}
}

class QuickSort extends SwapSort {
	
}

class HoareQuickSort extends QuickSort {
	private int split(int p, int r) {
		System.out.println("p: " + p + "\tr: " + r);
		printArray();		
		
		int i = p;
		int j = r + 1;
		do {
			do {
				++i;
			} while(m_array[i].lt(m_array[p]));
			do {
				--j;
			} while(m_array[j].gt(m_array[p]));
			if (i < j) {
				m_array[i].swap(m_array[j]);
			}
		} while (i < j);
		
		m_array[p].swap(m_array[j]);
		System.out.println("i: " + i + "\tj: " + j);
		printArray();
		return j;
	}
	
	private void sort(int p, int r) {
		if (p < r) {
			int j = split(p, r);
			sort(p, j-1);
			sort(j+1, r);
		}
	}
	
	public void sort() {
		sort(0, m_count-1);
	}
}


